\documentclass{article}

\usepackage{float}
\usepackage{datetime}
\usepackage{amsmath, amsthm, amssymb, bm, color, framed, graphicx, hyperref, mathrsfs, ctex, listings, pgfplots}

\usepackage{xcolor}
\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{ %
	backgroundcolor=\color{white},      % choose the background color
	basicstyle=\footnotesize\yahei,  % size of fonts used for the code
	columns=fullflexible,
	tabsize=4,
	breaklines=true,               % automatic line breaking only at whitespace
	captionpos=b,                  % sets the caption-position to bottom
	commentstyle=\color{mygreen},  % comment style
	escapeinside={\%*}{*)},        % if you want to add LaTeX within your code
	keywordstyle=\color{blue},     % keyword style
	stringstyle=\color{mymauve}\yahei,  % string literal style
	frame=single,
	rulesepcolor=\color{red!20!green!20!blue!20},
	% identifierstyle=\color{red},
	language=c++,
    numbers=left,
    escapeinside=``,
}



\title{Graph Report}
\author{叶睿浩		3190104031}
\date{\today}

\begin{document}
    \maketitle
    这是Bellman-Ford算法实现的report

    \section{实现Bellman-Ford算法}
    在完善了Graph模板类以后，在main函数中通过定义BF函数实现了Bellman-Ford算法。

    核心代码如下：

    \begin{lstlisting}[language=C++]
    double *d = new double[numV]; //d为distance数组
    for (int i=0; i<numV; i++)
        d[i] = INF;
    d[n] = 0;
    for (int i=0; i<numV; i++)
    {
        for (int j=0; j<numE; j++)
        {
            int u = list[j]->vertex;
            int v = list[j]->adjvex;
            if ( d[v]>(d[u]+list[j]->weight) )
                d[v] = d[u]+list[j]->weight;
        }
    }
    for (int j=0; j<numE; j++)
    {
        int u = list[j]->vertex;
        int v = list[j]->adjvex;
        if ( d[v]>(d[u]+list[j]->weight) )
        {
            cout << "存在负边环" << endl;
            for( int i=0; i<numE; i++ )
                delete[] list[i];
            delete[] list;
            return d;
        }
    }
    \end{lstlisting}
    
    在main函数中定义一个较小的图，打印全部的路径，确认能够输出正确结果。

    下面是numV=5,numE=8的无向图的一次计算结果。

    \begin{lstlisting}
    边如下： 
    0	( 0, 1, 79 )
    1	( 0, 3, 87 )
    2	( 0, 4, 95 )
    3	( 1, 2, 68 )
    4	( 1, 3, 82 )
    5	( 1, 4, 69 )
    6	( 2, 4, 2 )
    7	( 3, 4, 40 )
    节点如下： 
    0 1 2 3 4 
    从0出发最小距离: 
    0 79 97 87 95 
    从1出发最小距离: 
    79 0 68 82 69 
    \end{lstlisting}
    从结果中容易看出，函数输出结果正确

    \section{测试Bellman-Ford算法的效率}
    改变节点数和边数，得到以下计算结果：
    \begin{lstlisting}
    节点数：1000，边数：1000
    The average time: 8.487ms
    节点数：1000，边数：2000
    The average time: 13.878ms
    节点数：1000，边数：4000
    The average time: 25.189ms
    节点数：2000，边数：1000
    The average time: 20.628ms
    节点数：10000，边数：1000
    The average time: 279.737ms
        
    \end{lstlisting}

    测试结果制成图表如图1所示。
	\begin{figure}[!h] %插入图片
		\centering %图片居中
		
		\begin{tikzpicture} %tikz图片
			
			\begin{axis}[
				xlabel=节点数/边数, %横坐标名
				ylabel=Time(ms), %纵坐标名
				tick align=outside, %刻度在外显式
				legend style={at={(0.5,-0.2)},anchor=north} %图例在图下方显示
				]
				
				%第一条线，mark是折线标示形状
				\addplot[smooth,mark=*,blue] plot coordinates { 
					(1000,8.039)
					(2000,14.085)
					(4000,24.924)
					
				};
				
				%图例里名字
				\addlegendentry{改变边数大小}
				
				%第二条线，mark是折线标示形状
				
				\addplot[smooth,mark=triangle,cyan] plot coordinates {
					(1000,24.924)
					(2000,20.628)
					(10000,279.737)
				};
				\addlegendentry{改变节点数大小}
				
			\end{axis}
		\end{tikzpicture}
		\caption{程序验证}
		\label{fig1}
	\end{figure}
    从图中大致可以看出时间复杂度大概是$O(VE)$，这里关于节点数的影响似乎远大于边数。这实际上是由于我
    这里写的Bellman-Ford函数存在一个邻接矩阵转化为邻接表的额外开销所导致的。

    由于时间有限，关于这个问题的优化没有进行进一步的解决。

    \section{内存泄露检查}

    \begin{lstlisting}
    ==30227== HEAP SUMMARY:
    ==30227==     in use at exit: 0 bytes in 0 blocks
    ==30227==   total heap usage: 24,043 allocs, 24,043 frees, 856,530,432 bytes allocated
    ==30227== 
    ==30227== All heap blocks were freed -- no leaks are possible
    ==30227== 
    ==30227== Use --track-origins=yes to see where uninitialised values come from
    ==30227== For lists of detected and suppressed errors, rerun with: -s
    ==30227== ERROR SUMMARY: 9077 errors from 21 contexts (suppressed: 0 from 0)
    \end{lstlisting}

    没有内存泄露发生。



\end{document}